Many optimization problems (from academia or industry) require the use of a local search to find a satisfying solution in a\r\nreasonable amount of time, even if the optimality is not guaranteed. Usually, local search algorithms operate in a search space\r\nwhich contains complete solutions (feasible or not) to the problem. In contrast, in Consistent Neighborhood Search (CNS), after\r\neach variable assignment, the conflicting variables are deleted to keep the partial solution feasible, and the search can stop when all\r\nthe variables have a value. In this paper, we formally propose a new heuristic solution method, CNS, which has a search behavior\r\nbetween exhaustive tree search and local search working with complete solutions. We then discuss, with a unified view, the great\r\nsuccess of some existing heuristics, which can however be considered within the CNS framework, in various fields: graph coloring,\r\nfrequency assignment in telecommunication networks, vehicle fleet management with maintenance constraints, and satellite range\r\nscheduling. Moreover, some lessons are given in order to have guidelines for the adaptation of CNS to other problems.
Loading....